﻿// --------------------------------------------------------------------------------------------------------------------
// <copyright file="RedBlackTree.cs" company="Team Awesome">
//   Awesome
// </copyright>
// <summary>
//   Defines the RedBlackTree type.
//
//	 Commented out until work is resumed to avoid an overflow of warnings.
// </summary>
// --------------------------------------------------------------------------------------------------------------------

////namespace System.Collections.Generic
////{
////    using Diagnostics.Contracts;

////    /// <summary>
////    /// A red-black tree is a self-balancing binary search tree.
////    /// The tree shall always hold the following properties:
////    /// 1. A node is either red or black.
////    /// 2. The root is black. (This rule is sometimes omitted from other definitions. Since the root can always be changed from red to black but not necessarily vice-versa this rule has little effect on analysis.)
////    /// 3. All leaves are black.
////    /// 4. Both children of every red node are black.
////    /// 5. Every simple path from a given node to any of its descendant leaves contains the same number of black nodes.
////    /// </summary>
////    /// <typeparam name="T"> Type of items held in the tree nodes.
////    /// </typeparam>
////    public partial class RedBlackTree<T> where T : IComparable
////    {
////        /// <summary>
////        /// The tree's root node.
////        /// </summary>
////        private Node _root;

////        /// <summary>
////        /// Method for inserting a new item into the tree. This will automatically refactor the tree in order
////        /// for the invariances to be hold.
////        /// </summary>
////        /// <param name="item">
////        /// The item.
////        /// </param>
////        public void Add(T item)
////        {
////            #region Code Contracs: Pre - and Post conditions

////            // ReSharper disable CompareNonConstrainedGenericWithNull
////            Contract.Requires(item != null);

////            // ReSharper restore CompareNonConstrainedGenericWithNull
////            #endregion

////            _root = Add(_root, item);
////            _root.IsRed = false;
////        }

////        /// <summary>
////        /// Takes a node and tests if it should move further down the tree or if it should insert right away.
////        /// </summary>
////        /// <param name="node">
////        /// The node.
////        /// </param>
////        /// <param name="item">
////        /// The item.
////        /// </param>
////        /// <returns>
////        /// The inserted node.
////        /// </returns>
////        private static Node Add(Node node, T item)
////        {
////            #region Code Contracs: Pre - and Post conditions

////            // ReSharper disable CompareNonConstrainedGenericWithNull
////            Contract.Requires(item != null);

////            // ReSharper restore CompareNonConstrainedGenericWithNull
////            #endregion

////            if (node == null) return new Node(item);

////            var cmp = item.CompareTo(node.Item);

////            if (cmp < 0)
////                node.Left = Add(node.Left, item);
////            else if (cmp > 0)
////                node.Right = Add(node.Right, item);

////            return FixSetup(node);
////        }

////        /// <summary>
////        /// Validates the tree around the node and fixes everything not in place.
////        /// </summary>
////        /// <param name="node">
////        /// The node.
////        /// </param>
////        /// <returns>
////        /// The node corresponding to the same place in the tree.
////        /// </returns>
////        private static Node FixSetup(Node node)
////        {
////            #region Code Contracs: Pre - and Post conditions

////            Contract.Requires(node != null);
////            Contract.Ensures(Contract.Result<Node>() != null);
////            Contract.Ensures(!IsColourRed(Contract.Result<Node>().Right));

////            #endregion

////            if (IsColourRed(node.Right))
////                node = RotateLeft(node);
////            if (IsColourRed(node.Left) && IsColourRed(node.Left.Left))
////                node = RotateRight(node);
////            if (IsColourRed(node.Left) && IsColourRed(node.Right))
////                FlipColors(node);
////            return node;
////        }

////        /// <summary>
////        /// Flips the colors on the node and children of current node.
////        /// </summary>
////        /// <param name="node">
////        /// The node.
////        /// </param>
////        private static void FlipColors(Node node)
////        {
////            #region Code Contracs: Pre - and Post conditions

////            Contract.Requires(node != null);
////            Contract.Requires(node.Left != null);
////            Contract.Requires(node.Right != null);

////            Contract.Ensures(Contract.OldValue(node.IsRed) == !node.IsRed);
////            Contract.Ensures(Contract.OldValue(node.Left.IsRed) == !node.Left.IsRed);
////            Contract.Ensures(Contract.OldValue(node.Right.IsRed) == !node.Right.IsRed);

////            #endregion

////            node.IsRed = !node.IsRed;
////            node.Left.IsRed = !node.Left.IsRed;
////            node.Right.IsRed = !node.Right.IsRed;
////        }

////        /// <summary>
////        /// If the weight of the tree (or subtree) is on the left side, then we want to turn the tree to the right.
////        /// The roots left side node then becomes root itself and the old root takes the new roots right node.
////        /// </summary>
////        /// <param name="subRoot">
////        /// The sub Root.
////        /// </param>
////        /// <returns>
////        /// The new subroot.
////        /// </returns>
////        private static Node RotateRight(Node subRoot)
////        {
////            #region Code Contracs: Pre - and Post conditions

////            // We dont have any reason to turn the tree right if there are nothing on the left side.
////            Contract.Requires(subRoot != null);
////            Contract.Requires(subRoot.Left != null);

////            // subroot doesn't change node
////            Contract.Ensures(Contract.Result<Node>().Right.Equals(subRoot));
////            Contract.Ensures(Contract.OldValue(subRoot).Left.Equals(Contract.Result<Node>()));
////            Contract.Ensures(Contract.OldValue(subRoot).Right.Equals(subRoot.Right));
////            Contract.Ensures(Contract.OldValue(subRoot).Left.Right.Equals(subRoot.Left));
////            Contract.Ensures(Contract.OldValue(subRoot).Left.Left.Equals(Contract.Result<Node>().Left));

////            #endregion

////            var node = subRoot.Left;
////            subRoot.Left = node.Right;
////            node.Right = subRoot;
////            node.IsRed = subRoot.IsRed;
////            subRoot.IsRed = true;
////            return node;
////        }

////        /// <summary>
////        /// If the weight of the tree (or subtree) is on the right side, then we want to turn the tree to the left.
////        /// The roots right side node then becomes root itself and the old root takes the new roots left node.
////        /// </summary>
////        /// <param name="subRoot">
////        /// The sub Root.
////        /// </param>
////        /// <returns>
////        /// The new subroot.
////        /// </returns>
////        private static Node RotateLeft(Node subRoot)
////        {
////            #region Code Contracs: Pre - and Post conditions

////            // We dont have any reason to turn the tree left if there are nothing on the right side.
////            Contract.Requires(subRoot != null);
////            Contract.Requires(subRoot.Right != null);

////            // subroot doesn't change node
////            Contract.Ensures(Contract.Result<Node>().Left.Equals(subRoot));
////            Contract.Ensures(Contract.OldValue(subRoot).Right.Equals(Contract.Result<Node>()));

////            Contract.Ensures(Contract.OldValue(subRoot).Left == subRoot.Left);
////            Contract.Ensures(Contract.OldValue(subRoot).Right.Left.Equals(subRoot.Right));
////            Contract.Ensures(Contract.OldValue(subRoot).Right.Right.Equals(Contract.Result<Node>().Right));

////            #endregion

////            var node = subRoot.Right;
////            subRoot.Right = node.Left;
////            node.Right = subRoot;
////            node.IsRed = subRoot.IsRed;
////            subRoot.IsRed = true;
////            return node;
////        }

////        #region ContractInvariantMethod

////        // ReSharper disable UnusedMember.Local

////        /// <summary>
////        /// This method is used by code contracts to set all the invariants for the class.
////        /// </summary>
////        [ContractInvariantMethod]
////        private void ObjectInvariant()
////        {
////            // In our implementation every leaf is the value null and represents the black nil.

////            //// 1. A node is either red or black.
////            //// 2. The root is black. (This rule is sometimes omitted from other definitions. Since the root can always be changed from red to black but not necessarily vice-versa this rule has little effect on analysis.)
////            //// 3. All leaves are black.
////            //// 5. Every simple path from a given node to any of its descendant leaves contains the same number of black nodes.

////            // The root is black.
////            Contract.Invariant(this._root == null || !this._root.IsRed);

////            // No path from the root to the bottom contains two consecutive red links. 
////            ////Contract.Invariant(Contract.ForAll(this.GetEnumerator(), (Node x) => x.IsBlack || (!x.IsBlack && ((x.Left == null || x.Left.IsBlack) && (x.Right == null || x.Right.IsBlack)))));

////            Contract.Invariant(EqualAmountOfBlackNodes());

////            // There can't be any right leaning 3 nodes or 4 nodes in a 2-3 LLRB tree.
////            string failureCondition;
////            Contract.Invariant(CheckTreeColourStructure(out failureCondition), failureCondition);
////        }

////        // ReSharper restore UnusedMember.Local
////        #endregion
////    }
////}
